package leetcode.offer0039;

import java.util.Stack;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Offer39 implements IDebug {

	public int largestRectangleArea(int[] heights) {
		int len = heights.length;
		Stack<Integer> s = new Stack<>();
		int ans = 0;
		for (int i = 0; i < len; i++) {
			while (!s.isEmpty() && heights[s.peek()] > heights[i]) {
				int index = s.pop();// 当前坐标
				int h = heights[index];// 当前高度
				int l = s.isEmpty() ? -1 : s.peek();// l是左边第一个不可用的
				int r = i - 1;// r右边第一个可用的
				ans = Math.max(ans, (r - l) * h);// 以当前高度为高的最长矩形面积
			}
			s.add(i);
		}
		while (!s.isEmpty()) {
			int index = s.pop();// 当前坐标
			int h = heights[index];// 当前高度
			int l = s.isEmpty() ? -1 : s.peek();// l是左边第一个不可用的
			int r = len - 1;// 右边没有比当前index小的
			ans = Math.max(ans, (r - l) * h);
		}
		return ans;
	}

	@Override
	public void debug1() {
		String str = "[2,1,5,6,2,3]";
		int e = 10;
		int r = this.largestRectangleArea(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String str = "[2,4]";
		int e = 4;
		int r = this.largestRectangleArea(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		String str = "[4,2,0,3,2,5]";
		int e = 6;
		int r = this.largestRectangleArea(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Offer39 so = new Offer39();
		so.debug1();
		so.debug2();
		so.debug3();
	}

}
